#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct SSTable {
    ElemType lenth;
    ElemType *str;
} SSTable;

void SST_Init(SSTable &T, SSTable &T1, int len) {
    T1.lenth = T.lenth = len;
    T.str = (ElemType *) malloc(sizeof(ElemType) * T.lenth);
    T1.str = (ElemType *) malloc(sizeof(ElemType) * T1.lenth);

    for (int i = 0; i < T.lenth; i++) {
        int num;
        scanf("%d", &num);
        T.str[i] = T1.str[i] = num;
    }
}

void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

void array_print(SSTable T) {
    for (int i = 0; i < T.lenth; i++) {
        printf("%3d", T.str[i]);
    }
    printf("\n");
}

void AjustDown(ElemType *str, int pos, ElemType lenth) {
    int dad = pos;
    int son = dad * 2 + 1;
    while (son < lenth) {
        if (son + 1 < lenth && str[son] < str[son + 1]) {//如果左节点的值小于右节点的值
            son++;//往后移一位，将son++
        }
        if (str[dad] < str[son]) {//如果当前左节点的值是大于右节点的，则与父节点进行变比较
            swap(str[son], str[dad]);
            dad = son;//将son作为dad，继续调整为大根堆
            son = dad * 2 + 1;
        } else {
            break;
        }
    }
}

void HeapSort(ElemType *str, ElemType lenth) {
    int i;
    //先调整最后一棵子树
    for (i = (lenth - 1) / 2; i >= 0; i--) {
        AjustDown(str, i, lenth);
    }
    swap(str[0], str[lenth - 1]);//交换头和尾的值，完成第一次的子树调整
    for (i = lenth - 1; i > 1; i--) {
        AjustDown(str, 0, i);
        swap(str[0], str[i - 1]);
    }

}

void SelectSort(ElemType *str, ElemType lenth) {
    int i, j, min;
    for (i = 0; i < lenth - 1; i++) {
        min = i;
        for (j = i + 1; j < lenth; j++) {
            if (str[min] > str[j]) {
                min = j;
            }
        }
        if (min != i) {
            swap(str[min], str[i]);
        }
    }
}

int main() {
    SSTable T, T1;
    SST_Init(T, T1, 10);
    //选择排序
    SelectSort(T.str, T.lenth);
    array_print(T);
    //堆排序
    HeapSort(T1.str, T1.lenth);
    array_print(T1);
    return 0;
}
